package leetcodetree

import "math"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

const null = math.MaxInt32

func NewNode(data int) *TreeNode {
	if data == null {
		return nil
	} else {
		return &TreeNode{
			Val:   data,
			Left:  nil,
			Right: nil,
		}
	}
}

func NewTree(data []int) *TreeNode {
	index := 0
	queue := make([]*TreeNode, 0)
	root := NewNode(data[index])
	index++
	queue = append(queue, root)
	for index < len(data) {

		head := queue[0]
		if head == nil {
			queue = queue[1:]
			continue
		}
		queue = queue[1:]

		head.Left = NewNode(data[index])
		index++
		queue = append(queue, head.Left)
		if index < len(data) {
			head.Right = NewNode(data[index])
			index++
			queue = append(queue, head.Right)
		}
	}
	return root
}

func pathSum(root *TreeNode, targetSum int) [][]int {
	path := make([]int,0)
	res := make([][]int,0)
	count :=0
	traverse(root,count,targetSum,path,&res)
	return res
}

func traverse(root *TreeNode,count,target int,path []int,res *[][]int){
	if root == nil {
		return
	}

	count+=root.Val
	path = append(path,root.Val)
	if root.Left==nil && root.Right==nil{
		if count == target{
			*res = append(*res,append([]int{},path...))
		}
		return
	}
	traverse(root.Left,count,target,path,res)
	traverse(root.Right,count,target,path,res)


}
